from math import sqrt

def factorial(n):
    f = 1
    for x in xrange(2, n + 1):
        f *= x
    return f
    
def permutations(n, r=None):
    if r is None:
        r = n
    p = 1
    for x in xrange(n - r + 1, n + 1):
        p *= x
    return p
    
def combinations(n, k):
    return permutations(n, k) / factorial(k)
    
def geometric_mean(values):
    result = 1.0
    count = 0.0
    for num in values:
        result *= num
        count += 1.0
    return result ** (1.0 / count)
    
def least_squares(data):
    """An implementation of the least-squares method for finding the best linear function 
    approximation for a set of measurements (an iterable containing (x, y) tuples). This method 
    returns the constants 'a' and 'b' in the equation y = ax + b."""
    n = 0
    sum_x = 0.0
    sum_y = 0.0
    sum_xx = 0.0
    sum_xy = 0.0
    for x, y in data:
        n += 1
        sum_x += x
        sum_y += y
        sum_xx += x ** 2
        sum_xy += x * y
    a = (n * sum_xy - sum_x * sum_y) / (n * sum_xx - sum_x ** 2)
    b = (sum_xx * sum_y - sum_x * sum_xy) / (n * sum_xx - sum_x ** 2)
    return a, b
    
def confine(value, minimum, maximum):
    """Confine a value to a specified [min, max] range. This is a simple shortcut using the min() 
    and max() built-in functions."""
    return max(minimum, min(maximum, value))
    
def tobase(num, base=2):
    """Convert a number in decimal notation (a python integer) to a specified base. This function 
    returns a string representation of the number in the given base in the following format:
        [-]digits (base)
    First, a minus sign is placed at the front if the number is negative. Then a list of digits 
    appears. If the base is greater than 10, the digits are represented in decimal notation and 
    separated by spaces. Finally, the base is added between parentheses."""
    digits = []
    sign = ""
    if num < 0:
        sign = "-"
        num *= -1
    while num > 0:
        digits.append(str(num % base))
        num = int(num / base)
    digits.reverse()
    sep = " " if base > 10 else ""
    return "%s%s (%d)" % (sign, sep.join(digits), base)
    
def frombase(number_with_base):
    """Convert a number represented in an arbitrary base to decimal. The number representation 
    should follow the format of tobase(), i.e. '[+-]digits (base)'."""
    number, base = number_with_base.split("(")
    base = int(base[:-1])
    if base == 10:
        return int(number)
    sign = 1
    number = number.strip()
    if number[0] == "-":
        sign = -1
        number = number[1:]
    elif number[0] == "+":
        number = number[1:]
    n = 0
    digits = number
    if base > 10:
        digits = number.split(" ")
    exponent = len(digits) - 1
    for digit in digits:
        n += int(digit) * base ** exponent
        exponent -= 1
    return n * sign
    
    
class Compare(object):
    """A utility class implementing functions for comparing floats with a tolerance 'epsilon' that 
    is used as a trick to mitigate floating point arithmetic errors."""
    def __init__(self, epsilon=1e-9):
        self.epsilon = epsilon
        
    def eq(self, a, b):
        return abs(a - b) <= self.epsilon
        
    def neq(self, a, b):
        return not self.eq(a, b)
        
    def lt(self, a, b):
        return a < b - self.epsilon
        
    def leq(self, a, b):
        return a <= b + self.epsilon
        
    def gt(self, a, b):
        return a > b + self.epsilon
        
    def geq(self, a, b):
        return a >= b - self.epsilon
        
compare = Compare(epsilon=1e-9)
